import functools
class Solution(object):
    def maxDotProduct(self, nums1, nums2):
        n1 = len(nums1)
        n2 = len(nums2)
        @functools.cache
        def dfs(i, j):
            now_val = nums1[i] * nums2[j]
            if i == 0:
                if j == 0:
                    return now_val
                else:
                    return max(now_val, dfs(i, j - 1))
            else:
                if j == 0:
                    return max(now_val, dfs(i - 1, j))
                else:
                    return max(dfs(i, j - 1), dfs(i - 1, j), dfs(i - 1, j - 1) + now_val, now_val)

        return dfs(n1 - 1, n2 - 1)


data = Solution()
nums1 = [2,1,-2,5]
nums2 = [3,0,-6]
print(data.maxDotProduct(nums1, nums2))